package LeetCode;

import javax.swing.*;
import java.util.*;
public class LeetCodeMain18 {

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        backing(obstacleGrid,0,0);
        return res;
    }
    public boolean backing(int[][] obstacleGrid,int x,int y){
        if (x<0||x>= obstacleGrid.length||y<0||y>=obstacleGrid[0].length||obstacleGrid[x][y]!=0){
            return false;
        }
        res.add(Arrays.asList(x,y));
        if (x==obstacleGrid.length-1&&y==obstacleGrid[0].length-1){
            return true;
        }
        obstacleGrid[x][y]=2;
        if (backing(obstacleGrid,x+1,y)||backing(obstacleGrid, x, y+1)){
            return true;
        }
        res.remove(res.size()-1);
        return false;
    }
    List<List<Integer>> res=new ArrayList<>();
    public boolean isAdditiveNumber(String num) {
        return backtrack(num,0);
    }
    public boolean backtrack(String num,int startIndex){
        int size=res.size();
        if (startIndex==num.length()){
            return size>=3;
        }
        int max=num.charAt(startIndex)=='0'?startIndex+1:num.length();
        List<Integer> list=new ArrayList<>();
        for (int i = startIndex; i < max; i++) {
            list.add(0,num.charAt(i)-'0');
            if (size<2||check(res.get(size-2),res.get(size-1),list)){
                res.add(list);
                if (backtrack(num,i+1)){
                    return true;
                }
                res.remove(res.size()-1);
            }
        }
        return false;
    }
    public boolean check(List<Integer> num1, List<Integer> num2, List<Integer> list){
        List<Integer> ans=new ArrayList<>();
        int t=0;
        for (int i = 0; i < num1.size()||i<num2.size(); i++) {
            if (i<num1.size()){
                t+=num1.get(i);
            }
            if (i<num2.size()){
                t+=num2.get(i);
            }
            ans.add(t%10);
            t/=10;
        }
        if (t>0){
            ans.add(t);
        }
        boolean ok=ans.size()==list.size();
        for (int i = 0; i < list.size(); i++) {
            if (ans.get(i)!=list.get(i)){
                ok=false;
            }
        }
        return ok;
    }
}
